package algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author MaGuangQi
 * @description:验证二叉搜索树. 第98题
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 * @date 2020-06-28 20:47
 **/
public class ValidateTree {
    public boolean validate(TreeNode root) {
        if (root == null) {
            return true;
        }
        List<Integer> result = inOrder(root);
        for (int i = 0; i < result.size(); i++) {
            if (i < result.size() - 1 && result.get(i) >= result.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 解法一:使用中序遍历,判断遍历后返回的数组是否有序.
     * 左->根->右
     */
    public List<Integer> inOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return null;
        List<Integer> left = this.inOrder(root.left);
        result.addAll(left);
        result.add(root.val);
        List<Integer> right = this.inOrder(root.right);
        result.addAll(right);
        return result;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    /**
     * 解法一:优化, 使用中序遍历时,每次只需要判断当前节点的值是否大于上一次中序遍历后的值
     * 如果大于说明是有序的.也就是当前节点的值大于前继节点的值
     * 左->根->右
     */
    private Integer pre = Integer.MIN_VALUE;
    public boolean validate2(TreeNode root) {
        return inOrder2(root);
    }
    /**
    *中序遍历,只保留前继节点
    */
    public boolean inOrder2(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean left = inOrder2(root.left);
        //在遍历根节点的时候,需要判断一下当前节点的值是否小于等于前继节点
        if (root.val <= pre) {
            return false;
        }
        //否则,当前节点变为前继节点
        pre=root.val;
        boolean right = inOrder2(root.right);
        //只有左和右都满足的时候.
        return left && right;
    }

    /**
     * 解法二: 使用递归来解决,每次只要根节点在左子树和右子树的中间即可
     */
    public boolean helper(TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        //不为空才判断,也就是说min有值的时候才会进入判断,一开始都是null,所以if不进入.
        if (min!=null&&root.val<=min) return false;
        //不为空才判断,也就是说max有值的时候才会进入判断
        if (max!=null&&root.val>=max) return false;
        //递归左子树时,最小值保持不变. 递归右子树时,最大值保持不变
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
    public boolean validate3(TreeNode root) {
        return helper(root, null, null);
    }
}
